package jianzhioffer;

// 剑指 Offer 13. 机器人的运动范围
public class MovingCount {
    public static void main(String[] args) {
        System.out.println(new MovingCount().movingCount(2, 3, 1));
    }

    int _m;
    int _n;
    int count;
//    int[] dx = {-1, 0, 0, 1};
//    int[] dy = {0, 1, -1, 0};

    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        _m = m;
        _n = n;
        boolean[][] used = new boolean[m][n];
        dfs(0, 0, k, used);
        return count;
    }

    private void dfs(int x, int y, int k, boolean[][] used) {
        int _x = x;
        int _y = y;
        int xsum = 0;
        while (x > 0) {
            xsum += x % 10;
            x /= 10;
        }
        int ysum = 0;
        while (y > 0) {
            ysum += y % 10;
            y /= 10;
        }

        if (_x < 0 || _x >= _m || _y < 0 || _y >= _n || xsum + ysum > k || used[_x][_y]) {
            return;
        }
        used[_x][_y] = true;
        count++;
//        for (int i = 0; i < 4; i++) {
//            int mx = x + dx[i];
//            int my = y + dy[i];
//            dfs(mx, my, k, used);
//        }
        dfs(_x + 1, _y, k, used);
        dfs(_x, _y + 1, k, used);

    }



    public int movingCount2(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs2(0, 0, m, n, k, visited);
    }
    public int dfs2(int i, int j, int m, int n, int k, boolean[][] visited) {
        if(i >= m || j >= n || k < getSum(i) + getSum(j) || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs2(i + 1, j, m, n, k, visited) + dfs2(i, j + 1, m, n, k, visited);
    }

    private int getSum(int a) {
        int sum = a % 10;
        int tmp = a / 10;
        while(tmp > 0) {
            sum += tmp % 10;
            tmp /= 10;
        }
        return sum;
    }
}
